Trước khi có các nghiên cứu chuyên về độ phức tạp tính toán của các thuật toán, nhiều vấn đề cơ sở đã được các nhà nghiên cứu tìm hiểu. Có ảnh hưởng lớn nhất là định nghĩa máy Turing của Alan Turing năm 1936, một định nghĩa rất vững chắc và linh hoạt cho máy tính.

Theo Fortnow & Homer (2003), việc nghiên cứu có hệ thống độ phức tạp tính toán bắt đầu từ bài báo quan trọng mang tên "On the Computational Complexity of Algorithms" của Juris Hartmanis và Richard Stearns (1965). Bài báo này đã đưa ra định nghĩa của độ phức tạp thời gian và bộ nhớ và chứng minh các định lý cấp bậc.

Theo Fortnow & Homer (2003), các bài báo đầu tiên nghiên cứu các bài toán giải được bằng máy Turing với giới hạn tài nguyên bao gồm định nghĩa của John Myhill cho automat giới hạn tuyến tính (Myhill 1960), nghiên cứu của Raymond Smullyan về các tập hợp thô sơ (1961), bài báo của Hisao Yamada về tính toán thời gian thực (1962).[8] Trước đó, Boris Trakhtenbrot (1956), một nhà nghiên cứu tiên phong trong ngành ở Liên Xô, cũng đã nghiên cứu một thông số độ phức tạp khác.[9]

Năm 1967, Manuel Blum đã xây dựng các tiên đề cho lý thuyết độ phức tạp và chứng minh một kết quả quan trọng, nay gọi là định lý tăng tốc. Lý thuyết độ phức tạp bắt đầu phát triển mạnh sau khi nhà nghiên cứu Mỹ Stephen Cook và, một cách độc lập, nhà nghiên cứu Liên Xô Leonid Levin, chứng minh rằng tồn tại bài toán có liên hệ thực tế là NP-đầy đủ. Năm 1972, Richard Karp đã đưa ra một bước tiến lớn với bài báo "Reducibility Among Combinatorial Problems", trong đó ông chứng minh 21 bài toán rất khác nhau trong tổ hợp và lý thuyết đồ thị, tất cả đều rất nổi bật về độ khó, là NP-đầy đủ.[10]